import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shuang
 * @date 2022/5/1 22:17
 * 1402. 做菜顺序
 * https://leetcode-cn.com/problems/reducing-dishes/
 */
public class Solutions_1402 {
    public static void main(String[] args) {
        int[] satisfaction1 = {-1, -8, 0, 5, -9};  // output: 14  (-1*1 + 0*2 + 5*3 = 14)
        int[] satisfaction2 = {4, 3, 2};  // output: 20  (2*1 + 3*2 + 4*3 = 20)
        int[] satisfaction3 = {-1, -4, -5};  // output: 0

        List<int[]> inputs = new ArrayList<>();
        inputs.add(satisfaction1);
        inputs.add(satisfaction2);
        inputs.add(satisfaction3);

        for (int[] input : inputs) {
            int result = maxSatisfaction(input);
            System.out.println(result);
        }
    }

    /**
     * 1. 排序：据题意，可以按 任意 顺序安排做菜的顺序，则先进行排序，让最大的元素，在最后显示
     * 2. 定义一个 sum 变量：记录的是当前遍历元素 + 后面累加元素的和
     * 3. 倒序遍历：排序后，最大值一定在最后，所以倒序遍历
     * @param satisfaction
     * @return
     */
    public static int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int res = 0;
        int sum = 0;
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            sum += satisfaction[i];
            if (sum < 0) {
                // 已经小于 0 了，那么没必要再往前遍历了，再往前遍历的结果只会越来越小
                break;
            }
            res += sum;
        }
        return res;
    }
}

